class Solution {
public:
    vector<pair<int, int>> arr;
    pair<int, int> dp[20005];
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int head = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] != head)
            {
                head = nums[i];
                arr.push_back(pair<int, int>(head, head));
            }
            else arr.back().second += head;
        }
        return dfs(arr.size() - 1);
    }
    int dfs(int i)
    {
        if (i < 0) return 0;
        if (dp[i].first) return dp[i].second;
        int ans = dfs(i - 1);
        if (i > 0 && arr[i - 1].first == arr[i].first - 1) ans = max(ans, dfs(i - 2) + arr[i].second);
        else ans = max(ans, dfs(i - 1) + arr[i].second);
        dp[i].first = 1;
        return dp[i].second = ans;
    }
};